package tree;

import java.util.Objects;
import java.util.Stack;

public class TreeErddicThree {
    public static void main(String[] args) {
        Tree four = new Tree(4, null, null);
        Tree five = new Tree(5, null, null);
        Tree two = new Tree(2, four, five);
        Tree three = new Tree(3, null, null);
        Tree one = new Tree(1,two,three);
        System.out.println("先序");
        precedence(one);
        System.out.println();
        System.out.println("中序");
        inorder(one);
//        System.out.println();
//        System.out.println("后序");
//        followUp(one);
    }
    public static Stack<Tree> precedence(Tree tree){
        Stack<Tree> result = new Stack<>();
        result.push(tree);
        while (!result.empty()){
            Tree node = result.pop();
            System.out.print(node.getVal()+" ");
            if(!Objects.isNull(node.getRight())) result.push(node.getRight());
            if(!Objects.isNull(node.getLeft())) result.push(node.getLeft());
        }
        return result;
    }
    public static void inorder(Tree tree){
        Stack<Tree> result = new Stack<>();
        Tree node = tree;
        result.push(node);
        while (!result.empty()){
            node = result.peek();
            if(node != null){
                Tree pop = result.pop();
                if(pop.getRight() != null) result.push(pop.getRight());
                result.push(pop);
                result.push(null);
                if(pop.getLeft() != null) result.push(pop.getLeft());
            }else{
                result.pop();
                node = result.pop();
                System.out.print(node.getVal() + " ");
            }
        }
    }
    public static void followUp(Tree tree){
        Stack<Tree> result = new Stack<>();
        result.push(tree);
        while (!result.empty()){
            Tree node = result.peek();
            if(!Objects.isNull(node.getRight())) result.push(node.getRight());
            if(!Objects.isNull(node.getLeft())) result.push(node.getLeft());
            System.out.print(node.getVal()+" ");
        }
    }
}
